Hardware designs for integrated circuits, such as designs for system-on-chips (SoCs), typically implement one or more complex finite state machines (FSMs) which transition between states in response to input events in the hardware design and/or based on a computation on the internal state of the FSM.
The interplay between input events and computations based on the internal state of the FSM often results in dependencies, hazards and race conditions resulting in the FSM being in a livelock or a deadlock. A FSM is in deadlock if it has reached a state where no combination of inputs, or combination of internal state interactions, will cause the state to be exited (i.e. it is not possible to transition out of the state). In contrast, a FSM is in livelock if it can transition between states (i.e. it is not stuck in a single state as with deadlock), but it infinitely cycles through the same set of sets. For example, a FSM that infinitely cycles through three states A, B and C (e.g. A->B->C->A->B->C . . . ) is said to be in livelock.
Since it can be costly to discover, only after the hardware design is implemented in hardware (e.g. silicon), that it is prone to livelock, it is beneficial to identify livelock in a hardware design prior to implementing the hardware design in hardware.
The embodiments described below are provided by way of example only and are not limiting of implementations which solve any or all of the disadvantages of known methods and systems for detecting livelock in a hardware design.